public class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //移除链表元素
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur = head;
        if (head == null) {
            return head;
        }
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }

        }
        //处理头节点
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    //反转一个单链表
    public ListNode reverseList(ListNode head) {
    //判断链表是否为空,或者只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        //拿到head的下一个节点,对head进行头插
        ListNode cur = head.next;
        head.next = null;
        ListNode curNext;
        while (cur != null) {
            //保存cur下一个节点
            curNext = cur.next;
            //进行头插
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    //返回链表的中间结点
    //找中间节点法
    public ListNode middleNode(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        //中间节点
        int mid = count/2;
        cur = head;
        for(int i = 0; i<mid;i++) {
            cur = cur.next;
        }
        return cur;
    }
    //快慢指针法
    public ListNode middleNode1(ListNode head) {
        if(head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        //让快指针每次走两步，慢指针每次走一步
        //考虑链表长度奇偶
        while(fast != null && fast.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //输入一个链表，输出该链表中倒数第k个结点
    //求长度
    public int kthToLast(ListNode head, int k) {
        int size = 0;
        ListNode cur = head;
        while(cur != null) {
            size++;
            cur = cur.next;
        }
        //cur回到头节点，走size-k步到达倒数第k个节点
        cur = head;
        for(int i = 0; i < size-k; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
    //快慢指针
    public int kthToLast1(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        //让fast领先slow k-1步
        for(int i = 0; i < k-1; i++) {
            fast = fast.next;
        }
        //fast和slow一起走
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        //slow最后停留到达的位置是倒数第k个节点
        return slow.val;
    }
}
